<html>
<head>
  <title>Graph</title>
  <basefont face="微软雅黑" size="2" />
  <meta http-equiv="Content-Type" content="text/html;charset=utf-8" />
  <meta name="exporter-version" content="Evernote Windows/307027 (zh-CN, DDL); Windows/6.1.0 (Win32);"/>
  <style>
    body, td {
      font-family: 微软雅黑;
      font-size: 10pt;
    }
  </style>
</head>
<body>
<a name="577"/>
<h1>Graph</h1>

<div>
<span><div><h1><span style="color: rgb(28, 51, 135); font-size: 16pt;"><br/></span></h1><div><ul><li><span style="color: rgb(28, 51, 135); font-size: 16pt; line-height: 1.45;">理解图的概念及使用</span><br/></li><li><span style="color: rgb(28, 51, 135); font-size: 16pt; line-height: 1.45;">通过多种方法实现图抽象数据类型</span><br/></li><li><span style="color: rgb(28, 51, 135); font-size: 16pt; line-height: 1.45;">了解图如何用于解决不同领域的问题</span><br/></li></ul></div><div><span style="font-size: 16pt; color: rgb(28, 51, 135);">图是比我们上一章学习的树更普遍的结构，事实上你可以认为树是一种特殊的图。图可以被用来表述世界上很多有趣的事情，包括道路系统，城市间航线，因特网的联接，甚至是你完成计算机科学学位所必修的课程顺序。我们在这一章将看到一旦我们很好地表述了某个问题，我们可以使用标准的图算法来解决一些看起来非常困难的问题。</span></div><div><br/></div><div><br/></div><h1><span style="color: rgb(28, 51, 135);"><font style="font-size: 18pt;">Graph - 图</font></span></h1><div style="margin-top: 1em; margin-bottom: 1em;">图的表示通常使用<span style="font-weight: bold;">邻接矩阵和邻接表</span>，前者易实现但是对于稀疏矩阵会浪费较多空间，后者使用链表的方式存储信息但是对于图搜索时间复杂度较高。</div><div style="margin-top: 1em; margin-bottom: 1em;"><table style="border-collapse: collapse; min-width: 100%;"><colgroup><col style="width: 149px;"></col><col style="width: 409px;"></col></colgroup><tbody><tr><td style="width: 149px; padding: 8px; border: 1px solid rgb(204, 204, 204);"><div>概念词</div></td><td style="width: 409px; padding: 8px; border: 1px solid rgb(204, 204, 204);"><div>定义</div></td></tr><tr><td style="width: 149px; padding: 8px; border: 1px solid rgb(204, 204, 204);"><div><span>顶点</span> <span>Vertex</span></div></td><td style="width: 409px; padding: 8px; border: 1px solid rgb(204, 204, 204);"><div>顶点（也称“节点 node”）是图的基础部分。它具有<font style="color: rgb(227, 0, 0);"><b>名称标识</b><b>“key”</b></font>。顶点也可以有<b><font style="color: rgb(227, 0, 0);">附加的信息项“playload”</font></b>。</div></td></tr><tr><td style="width: 149px; padding: 8px; border: 1px solid rgb(204, 204, 204);"><div><span>边</span> <span>Edge</span></div></td><td style="width: 409px; padding: 8px; border: 1px solid rgb(204, 204, 204);"><div><span>图的另一个基础组成部分。<span>如果一条边连接两个顶点，则表示两者具有联系。边可以是单向的，也可以是双向的。如果一个图中的边都是单向的，我们就说这个图是</span><span>“</span><span>有向图</span> <span>directed graph/digraph”</span><span>。</span></span></div></td></tr><tr><td style="width: 149px; padding: 8px; border: 1px solid rgb(204, 204, 204);"><div><span>权重</span> <span>Weight</span></div></td><td style="width: 409px; padding: 8px; border: 1px solid rgb(204, 204, 204);"><div><span>为了表达从一个顶点到另一个顶点的</span><span>“</span><span>代价</span><span>”</span><span>，可以给边赋权。例如，一个连接两个城市的道路图中，两个城市之间的距离就可以作为边的权重。</span></div></td></tr><tr><td style="width: 149px; padding: 8px; border: 1px solid rgb(204, 204, 204);"><div><span>图可以用</span> <span>G=(V,E)</span><span>来表述</span></div></td><td style="width: 409px; padding: 8px; border: 1px solid rgb(204, 204, 204);"><div><span>V</span><span>是顶点的集合，</span><span>E</span><span>是边的集合。每个边是一个元组</span><span>(v, w)</span><span>，</span><span>w, v</span><span>∈</span><span>V。</span></div><div><span>我们可以在边元组中加入第三个要素来表述权重。</span></div></td></tr><tr><td style="width: 149px; padding: 8px; border: 1px solid rgb(204, 204, 204);"><div>路径 Path</div></td><td style="width: 409px; padding: 8px; border: 1px solid rgb(204, 204, 204);"><div><span>由边依次连接起来的顶点序列。</span></div><div><span>我们将路径定义为</span> <span>P=(w1, w2,…, wn)</span><span>，其中对于所有</span> <span>1&lt;=i&lt;=n-1, (wi, wi+1)</span> <span>∈</span> <span>E</span><span>。</span></div><div><span>无权路径的长度为边的数量，等于</span> <span>n-1</span><span>。</span></div><div><span>带权路径的长度为所有边权重之和。</span></div></td></tr><tr><td style="width: 149px; padding: 8px; border: 1px solid rgb(204, 204, 204);"><div><span>圈</span> <span>Cycle</span></div></td><td style="width: 409px; padding: 8px; border: 1px solid rgb(204, 204, 204);"><div><span>有向图里的圈是首尾顶点相同的路径。</span></div><div><span>没有圈的图称为</span><span>“</span><span>无圈图</span> <span>acyclic graph”</span></div><div><span>没有圈的有向图称为</span><span>“</span><span>有向无圈图</span> <span>directed acyclic graph</span><span>或</span> <span>DAG”</span></div></td></tr></tbody></table><div><span>图</span> <span>7.2</span><span>展现了另一个简单有向赋权图。这个图可以表示成</span><span>6</span><span>个顶点：</span></div><div><span>V={V0, V1, V2, V3, V4, V5}</span></div><div><span>及</span><span>9</span><span>条边的集合：</span></div><div><span>E={(v0,v1,5),(v1,v2,4),(v2,v3,9),(v3,v4,7),(v4,v0,1),(v0,v5,2),(v5,v4,8),(v3,v5,3),(v5,v2,1)}</span></div><div><img src="Graph_files/Image.png" type="image/png" data-filename="Image.png" width="295"/></div><div><span>图</span> <span>7.2</span><span>有向图的简单例子</span></div><div><span>图</span> <span>7.2</span><span>中的图展现了其他两个重要的图的术语：</span></div><div><br/></div></div><div style="margin-top: 1em; margin-bottom: 1em;"><br/></div><div style="margin-top: 1em; margin-bottom: 1em;"><font color="#1C3387" style="font-size: 18pt;"><b>图抽象数据类型</b></font></div><div style="margin-top: 1em; margin-bottom: 1em;"><table style="border-collapse: collapse; min-width: 100%;"><colgroup><col style="width: 215px;"></col><col style="width: 300px;"></col></colgroup><tbody><tr><td style="width: 215px; padding: 8px; border: 1px solid rgb(204, 204, 204);"><div>ADT</div></td><td style="width: 300px; padding: 8px; border: 1px solid rgb(204, 204, 204);"><div>定义</div></td></tr><tr><td style="width: 215px; padding: 8px; border: 1px solid rgb(204, 204, 204);"><div><span>Graph()</span></div></td><td style="width: 300px; padding: 8px; border: 1px solid rgb(204, 204, 204);"><div><span>创建一个空的图</span></div></td></tr><tr><td style="width: 215px; padding: 8px; border: 1px solid rgb(204, 204, 204);"><div><span>addVertex(vert)</span></div></td><td style="width: 300px; padding: 8px; border: 1px solid rgb(204, 204, 204);"><div><span>将一个顶点</span> <span>Vertex</span><span>对象加入图中</span></div></td></tr><tr><td style="width: 215px; padding: 8px; border: 1px solid rgb(204, 204, 204);"><div><span>addEdge(fromVert, toVert)</span></div></td><td style="width: 300px; padding: 8px; border: 1px solid rgb(204, 204, 204);"><div><span>添加一条有向边</span></div></td></tr><tr><td style="width: 215px; padding: 8px; border: 1px solid rgb(204, 204, 204);"><div><span>addEdge(fromVert, toVert, weight)</span></div></td><td style="width: 300px; padding: 8px; border: 1px solid rgb(204, 204, 204);"><div><span>添加一条带权的有向边</span></div></td></tr><tr><td style="width: 215px; padding: 8px; border: 1px solid rgb(204, 204, 204);"><div><span>getVertex(vertKey)</span></div></td><td style="width: 300px; padding: 8px; border: 1px solid rgb(204, 204, 204);"><div><span>查找图中名称为</span> <span>vertKey</span><span>的顶点</span></div></td></tr><tr><td style="width: 215px; padding: 8px; border: 1px solid rgb(204, 204, 204);"><div><span>getVertices()</span></div></td><td style="width: 300px; padding: 8px; border: 1px solid rgb(204, 204, 204);"><div><span>返回图中所有顶点列表</span></div></td></tr><tr><td style="width: 215px; padding: 8px; border: 1px solid rgb(204, 204, 204);"><div><span>in</span></div></td><td style="width: 300px; padding: 8px; border: 1px solid rgb(204, 204, 204);"><div><span>按照</span> <span>vert in graph</span><span>的语句形式，返回顶点是否存在图中。如果存在则返回</span><span>True</span><span>，否则返回</span><span>False</span></div></td></tr></tbody></table><div>有几种方法可以在 Python实现图抽象数据结构（ADT），需要在不同的应用中加以权衡。<b><font style="color: rgb(227, 0, 0);"><font style="font-size: 12pt;">图的实现有两个著名的方法，邻接矩阵</font> <font style="font-size: 12pt;"><span>adjacency matrix</span><span>和邻接表</span> <span>adjacency list</span></font></font></b>。我们将说明这两种不同的选择，并作为 Python的类来实现邻接矩阵。</div></div><div style="margin-top: 1em; margin-bottom: 1em;"><br/></div><div style="margin-top: 1em; margin-bottom: 1em;"><br/></div><h2><span style="color: rgb(28, 51, 135);"><font style="font-size: 18pt;">编程实现</font></span></h2><h3><font style="font-size: 16pt; color: rgb(227, 0, 0);">邻接矩阵</font></h3><div>设顶点个数为 V, 那么邻接矩阵可以使用 V × V 的二维数组来表示。</div><div><span style="font-weight: bold; color: rgb(173, 0, 0);">g[i][j]</span><span style="font-weight: bold; color: rgb(173, 0, 0);">表示顶点</span><span style="font-weight: bold; color: rgb(173, 0, 0);">i</span><span style="font-weight: bold; color: rgb(173, 0, 0);">和顶点</span><span style="font-weight: bold; color: rgb(173, 0, 0);">j</span><span style="font-weight: bold; color: rgb(173, 0, 0);">的关系，</span>对于无向图可以使用0/1表示是否有连接，对于带权图则需要使用INF来区分。有重边时保存边数或者权值最大/小的边即可。</div><h4>Python</h4><div style="box-sizing: border-box; padding: 8px; font-size: 12px; border-top-left-radius: 4px; border-top-right-radius: 4px; border-bottom-right-radius: 4px; border-bottom-left-radius: 4px; background-color: rgb(251, 250, 248); border: 1px solid rgba(0, 0, 0, 0.14902);"><div><span style="font-size: medium; background-color: rgb(251, 250, 248); color: rgb(0, 0, 0); font-family: 微软雅黑; line-height: 18px;">g = [[0 for _ in range(V)] for _ in range(V)]</span></div></div><h3><span style="color: rgb(28, 51, 135); font-size: 16pt;"><br/></span></h3><h3><span style="color: rgb(28, 51, 135); font-size: 16pt;">邻接表</span></h3><div style="margin-top: 1em; margin-bottom: 1em;"><span>一个实现稀疏图的更高效的方案是使用邻接表</span> <span>adjacency list</span><span>。在这个实现方法中，我们维护一个包含所有顶点的主列表（</span><span>master list</span><span>），主列表中的每个顶点，再关联一个与自身有边连接的所有顶点的列表。在实现顶点类的方法里，我们使用字典而不是列表，此时字典中的键（</span><span>key</span><span>）对应顶点标识，而值（</span><span>value</span><span>）则可以保存顶点连接边的权重。图</span><span>7. 4</span><span>展现了图</span><span>7.2</span><span>中图的邻接表。</span><br/></div><div style="margin-top: 1em; margin-bottom: 1em;"><span><img src="Graph_files/Image [1].png" type="image/png" data-filename="Image.png" width="391"/><br/></span></div><h3><span style="font-weight: bold; font-size: 14pt;">在我们实现图表抽象数据类型时，我们可以<font color="#E30000">创建两个类，</font></span><font color="#E30000"><span style="font-weight: bold; font-size: 14pt;">Graph</span><span style="font-weight: bold; font-size: 14pt;">和</span> <span style="font-weight: bold; font-size: 14pt;">Vertex</span></font><span style="font-weight: bold; font-size: 14pt;">（详见表一和表二）。</span></h3><h3><span style="font-size: 12pt; font-weight: normal; line-height: 1.45;">Graph</span><span style="font-size: 12pt; font-weight: normal; line-height: 1.45;">保存了包含所有顶点的主表，</span><span style="font-size: 12pt; font-weight: normal; line-height: 1.45;">Vertex</span><span style="font-size: 12pt; font-weight: normal; line-height: 1.45;">则描绘了图表中顶点的信息。</span></h3></div><div><span>每一个</span><span>Vertex</span><span>使用一个字典来记录顶点与顶点间的连接关系和每条连接边的权重，这个字典被称作</span><span>connectionTo</span><span>（</span><span>self. connectionTo</span><span>）。</span></div><div><span>构造函数（</span><span>__init___</span><span>）简单地初始化了（一般为字符串的）</span><span>id</span><span>和</span> <span>connectionTo</span><span>字典。</span></div><div><span>addNeighbor</span><span>方法被用来添加从一个顶点到另一个顶点的连接。</span></div><div><span>getConnections</span><span>方法用以返回以</span><span>connectionTo</span><span>字典中的实例变量所表示的邻接表中的所有顶点。</span></div><div><span>getWeight</span><span>方法可以通过一个参数返回顶点与顶点之间的边的权重。</span></div><div style="box-sizing: border-box; padding: 8px; font-family: Monaco, Menlo, Consolas, &quot;Courier New&quot;, monospace; font-size: 12px; color: rgb(51, 51, 51); border-top-left-radius: 4px; border-top-right-radius: 4px; border-bottom-right-radius: 4px; border-bottom-left-radius: 4px; background-color: rgb(251, 250, 248); border: 1px solid rgba(0, 0, 0, 0.14902); background-position: initial initial; background-repeat: initial initial;-en-codeblock:true;"><div>class Vertex:</div><div><span>    def __init__(self, key):</span><br/></div><div><span><span>    <span>    self.id = key</span></span><br/></span></div><div><span><span>    <span>    self.connectedTo = {}</span></span><br/></span></div><div><span><span>    def addNeighborf(self, nbr, weight=0):</span><br/></span></div><div><span><span>    <span>    self.connectedTo[nbr] = weight</span></span><br/></span></div><div><span>    def __str__(self):</span></div><div><span><span>    <span>    return str(self.id) + ' connectedTo: ' + str([x.id for x in self.connectedTo])</span></span><br/></span></div><div><span><span>    def getConnections(self):</span><br/></span></div><div><span><span>    <span>    return self.connectedTo.keys()</span></span><br/></span></div><div><span><span>    def getId(self):</span><br/></span></div><div><span><span>    <span>    return self.id</span></span><br/></span></div><div><span><span>    def getWeight(self, nbr):</span><br/></span></div><div><span><span>    <span>    return self.connectedTo[nbr]</span></span><br/></span></div></div><div><br/></div><div><span>下表实现的</span> <span>Graph</span> <span>类，包含了一个将顶点名称映射到顶点对象的字典。</span></div><div><span>Graph</span> <span>也提供了向图中添加顶点和将一个顶点与另一个连接起来的方法。</span></div><div><span>getVertices</span> <span>方法可以返回图中所有顶点的名称。</span></div><div><span>实现</span><span>__iter__</span><span>方法简化对特定图中所有顶点对象的遍历。</span></div><div style="box-sizing: border-box; padding: 8px; font-family: Monaco, Menlo, Consolas, &quot;Courier New&quot;, monospace; font-size: 12px; color: rgb(51, 51, 51); border-top-left-radius: 4px; border-top-right-radius: 4px; border-bottom-right-radius: 4px; border-bottom-left-radius: 4px; background-color: rgb(251, 250, 248); border: 1px solid rgba(0, 0, 0, 0.14902); background-position: initial initial; background-repeat: initial initial;-en-codeblock:true;"><div>class Graph:</div><div><span>    def __init__(self):</span><br/></div><div><span><span>    <span>    self.vertList = {}</span></span><br/></span></div><div><span><span>    <span>    self.numVertices = 0</span></span><br/></span></div><div><span><span>    def addVertex(self, key):</span><br/></span></div><div><span><span>    <span>    self.numVertices = self.numVertices + 1</span></span><br/></span></div><div><span><span>    <span>    newVertex = Vertex(key)</span></span><br/></span></div><div><span><span>    <span>    self.vertList[key] = newVertex</span></span><br/></span></div><div><span><span>    <span>    return newVertex</span></span><br/></span></div><div><span><span>    def getVertex(self, n):</span><br/></span></div><div><span><span>    <span>    if n in self.vertList:</span></span><br/></span></div><div><span><span>    <span>    <span>    return self.vertList[n]</span></span></span><br/></span></div><div><span><span>    <span>    else:</span></span><br/></span></div><div><span><span>    <span>    <span>    return None</span></span></span><br/></span></div><div><span><span>    def __contains__(self, n):</span><br/></span></div><div><span><span>    <span>    return n in self.vertList</span></span><br/></span></div><div><span><span>    def addEdge(self, f, t, cost=0):</span><br/></span></div><div><span><span>    <span>    if f not in self.vertList:</span></span><br/></span></div><div><span><span>    <span>    <span>    nv = self.addVertex(f)</span></span></span><br/></span></div><div><span><span>    <span>    if t not in self.vertList:</span></span><br/></span></div><div><span><span>    <span>    <span>    nv = self.addVertex(t)</span></span></span><br/></span></div><div><span><span>    <span>    <span>    self.vertList[f].addNeighbor(self.vertList[t], cost)</span></span></span><br/></span></div><div><span><span>    def getVertices(self):</span><br/></span></div><div><span><span>    <span>    return self.vertList.keys()</span></span><br/></span></div><div><span><span>    def __iter__(self):</span><br/></span></div><div><span><span>    <span>    return iter(self.vertList.values())</span></span><br/></span></div></div><div><br/></div><div><br/></div><div><br/></div><div><br/></div><div><br/></div><div><font color="#1C3387" style="font-size: 18pt;"><b><span>WORD LADDER</span> <span>词梯问题</span></b></font></div><div><br/></div><div><span>比如，将单词“ FOOL”转变成单词“ SAGE”。在词梯问题中，你必须以一次只改变一个字母的方式来逐步转变单词。每一步你都必须将一个单词转变成另一个单词，并且不允许转变成一个不存在的单词。</span></div><div><span>在两个仅差一个字母的单词之间连一条边。如果我们可以创建一个这样的图表，那么任一从一个单词到另一个单词的路径都是某个词梯问题的一个解。</span></div><div><img src="Graph_files/Image [2].png" type="image/png" data-filename="Image.png"/></div><div><ul><li><span>先假设我们有一个单词列表,其中的单词都是一样长。</span></li><li><span>为列表里的每个单词在图中创建一个顶点。</span></li><li><span>而为将这些单词连接起来，我们可以将列表中的每个词与所有其他单词比较。当我们比较的时候，我们想要看到有多少字母是不同的。如果这两个词只有一个字母不同，我们就可以在图中创建一条连接它们的边。</span></li><li><span>假设我们有非常多的桶,每个桶外都贴有一个四个字母的单词标签，并且标签上有且仅有一个字母被‘ _’(通配符)所代替。例如，考虑图7.6,我们就可能会将一个桶贴上“ pop_”， 当我们处理我们的列表中的每个词，都将其与每个桶比较，使用“_” 作为一个通配符,那么“pope” 和“ pops” 都与“ pop_”匹配。每次我们找到一个匹配的桶,我们把单词放在桶里。一旦我们把所有单词都放在适当的桶里，我们便知道，同一个桶里的所有单词都是相互连接的。</span></li></ul></div><div><img src="Graph_files/Image [3].png" type="image/png" data-filename="Image.png" width="366"/></div><div><br/></div><div><br/></div><div><br/></div><div><br/></div><div><span><font style="font-size: 18pt; color: rgb(28, 51, 135);"><b>实现广度优先搜索(BFS)</b></font></span></div><div><br/></div><div><span>在建立了词梯问题的图之后，我们就能把注意力转向寻找最短单词变化序列的算法，我们将要用到的这一图算法被称作广度优先搜索(BFS)算法。</span></div><div><span>已知一个图 G 和它的一个起始顶点 s，广度优先搜索(BFS)通过搜索图中的边来找到图G中所有和s有路径相连的顶点。</span></div><div><span><font style="font-size: 12pt; color: rgb(227, 0, 0);"><b>其显著的特点是在搜索达到距离 k+1 的顶点之前，BFS会找到全部距离为 k 的顶点。</b></font></span></div><div><br/></div><div><span>有一个很好的方法去想象广度优先搜索（BFS）的运行原理，那就是建造一棵以 s 为根的树的过程，一次建造树的一层，同时，广度优先搜索(BFS)在增加层次前，会保证将始顶点所有的子顶点都添加在了树中。</span></div><div><br/></div><div><span>为了进一步追踪这一过程，这里的 BFS 算法在搜索过程中，会给每一个顶点染色为白色、灰色或黑色。</span></div><div><br/></div><div><span>每一个顶点在被构建时都被初始化为白色，在这之后，白色代表的是尚未被发现的顶点。当一个顶点被第一次发现后，它被染成灰色</span></div><div><br/></div><div><span>当广度优先搜索(BFS)完全探索完一个顶点后，它被染成黑色。</span></div><div><br/></div><div><span>这意味着一旦一个节点染成了黑色，它就没有邻近的白色节点；而另一方面，如果一个顶点被标识为了灰色，这就意味着其附近可能还存在着未探索的顶点等待被探索。</span></div><div><br/></div><div><span>广度优先搜索（BFS） 从起始顶点 s 开始，此时 s 的颜色被设置为灰色，代表它现在已经被发现了，另外两个参数——距离和父顶点，对于起始节点 s 初始设置为了 0 和 None。随后，起始节点会被加入到一个队列中，下一步便是系统地探索队首顶点。这个过程通过迭代（遍历）队首顶点的邻接列表来完成，每检查邻接表中的一个顶点，便会维护这个顶点的颜色参量，如果颜色是白色的，就说明这个节点尚未被探索，也就会按下述四步操作：</span></div><div><span>1、 新的未探索的顶点 nbr，标记为灰色；</span></div><div><span>2、 nbr 的父顶点被设置为当前节点 currentVert；</span></div><div><span>3、 nbr 的距离被设置为当前节点的距离加一；</span></div><div><span>4、 nbr 被加入队尾，这一操作使得直到 nbr 在当前顶点的邻接列表中的所有顶点被搜索完后，才能够进行下一层次的探索操作。</span></div><div><br/></div><div><br/></div><div><br/></div><div><br/></div><div><br/></div><div><span><font style="font-size: 18pt; color: rgb(28, 51, 135);"><b>骑士周游问题</b></font></span></div><div><span>骑士周游问题是在国际象棋棋盘上仅用“骑士”这个棋子进行操作。问题的目的是找到一条可以让骑士访问所有格子，并且每个格子只能走一次的走棋序列。一个这样的走棋序列称为一次“周游”。</span></div><div><br/></div><div><span>尽管现在研究人员已经研究了很多不同的算法来解决骑士周游问题，图搜索依旧是最便于理解和编写的算法之一。</span></div><div><span><br/></span></div><div><ul><li><span style="line-height: 1.45;">将棋盘上合法的走棋次序表示为一个图</span><br/></li><li><span style="line-height: 1.45;">采用图搜索算法搜寻一个长度为（行×列 - 1）的路径，此路径上恰包含每个顶点一次</span><br/></li></ul></div><div><br/></div><div><br/></div><div><br/></div><div><br/></div><div><br/></div><div><br/></div><div><br/></div><div><br/></div><div><br/></div><div><br/></div><div><br/></div><div><br/></div><div><br/></div><div><br/></div><div><br/></div><div><br/></div><div><br/></div><div><br/></div><div><br/></div><div><br/></div><div><br/></div><div><br/></div><div><br/></div><div><br/></div><div><br/></div><div><br/></div><div><br/></div><div><br/></div></span>
</div></body></html> 